import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-07-11
 * Time:22:18
 */


public class AlgorithmsTwo {
    public boolean Find(int target, int[][] array) {
        int i = 0;
        int j = array[0].length - 1;
        boolean ans = false;
        while (i >= 0 && i < array.length && j >= 0 && j < array[0].length) {
            if (array[i][j] > target) {
                j--;
            } else if (array[i][j] < target) {
                i++;
            } else {
                ans = true;
                break;
            }
        }
        return ans;
    }

    public String replaceSpace(StringBuffer str) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                builder.append("%20");
            } else {
                builder.append(str.charAt(i));
            }
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ArrayList<Integer> arrayList = new ArrayList<>();
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        System.out.println(printListFromTailToHead(listNode));
    }

    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        return TailToHead(listNode);
    }

    private static ArrayList<Integer> TailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if (listNode == null) {
            return arrayList;
        }
        arrayList.addAll(TailToHead(listNode.next));
        arrayList.add(listNode.val);
        return arrayList;
    }


    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        if (pre.length == 0 || vin.length == 0) {
            return null;
        }
        return reConstructBinaryTreeCore(pre, 0, pre.length - 1, vin, 0, vin.length - 1);
    }

    private TreeNode reConstructBinaryTreeCore(int[] pre, int preStart, int preEnd,
                                               int[] vin, int vinStart, int vinEnd) {
        if (preStart > preEnd || vinStart > vinEnd) {
            return null;
        }
        TreeNode root = new TreeNode(pre[preStart]);
        int i = vinStart;
        for (; i <= vinEnd; i++) {
            if (vin[i] == pre[preStart]) {
                root.left = reConstructBinaryTreeCore(pre,preStart+1,i-vinStart+preStart,
                        vin,vinStart,i-1);
                root.right = reConstructBinaryTreeCore(pre,i-vinStart+preStart+1,
                        preEnd,vin,i+1,vinEnd);
                break;
            }
        }
        return root;
    }

    public int minNumberInRotateArray(int [] array) {
        Arrays.sort(array);
        return array[0];
    }

    public int Fibonacci(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        int a = 1;
        int b = 1;
        int ans = 0;
        while (n > 2) {
            n--;
            ans = a + b;
            b = a;
            a = ans;
        }
        return ans;
    }
    public int jumpFloor(int target) {
        if (target == 1 || target == 2 || target == 0) {
            return target;
        }
        int a = 1;
        int b = 2;
        int ans = 0;
        while (target > 2) {
            target--;
            ans = a + b;
            a = b;
            b = ans;
        }
        return ans;
    }
}
